Soal dan Pembahasan – Kombinatorika (Tingkat Lanjut)

Ada $P(S) = 6^6$ susunan untuk kasus ini.
Kemungkinan munculnya jumlah mata dadu $9$ adalah sebagai berikut (masing-masing angka merepresentasikan setiap mata dadu yang muncul).
$1~1~1~1~1~4$ sebanyak $\dfrac{6!}{5!} = 6$ susunan.
$1~1~1~1~2~3$ sebanyak $\dfrac{6!}{4!} = 30$ susunan.
$1~1~1~2~2~2$ sebanyak $\dfrac{6!}{3! \cdot 3!} = 20$ susunan.
Semua susunan yang mungkin adalah $6 + 30 + 20 = 56$ susunan sehingga peluang munculnya jumlah mata dadu $9$ adalah $\boxed{P(9) = \dfrac{56}{6^6}}$

Karena setiap persegi panjang yang diberikan memiliki ukuran panjang yang sama, yaitu $2$, maka kita hanya perlu meninjau ukuran lebarnya. Untuk mengisi persegi panjang berukuran $2 \times 16$ tersebut, kita perlu menentukan nilai $a, b, c \in \mathbb{N}$ sehingga persamaan berikut berlaku.
$2a + 3b + 4c = 16$
Tabel berikut menyatakan kombinasi nilai $a, b, c$ yang mungkin untuk memenuhi persamaan di atas.
$\begin{array}{|c|c|c|} \hline \text{Nilai}~a &  \text{Nilai}~b &  \text{Nilai}~c \\ \hline 0 & 0 & 4 \\ 2 & 0 & 3 \\ 1 & 2 & 2 \\ 4 & 0 & 2 \\ 0 & 4 & 1 \\ 3 & 2 & 1 \\ 6 & 0 & 1 \\ 2 & 4 & 0 \\ 5 & 2 & 0 \\ 8 & 0 & 0 \\ \hline \end{array}$
Jadi, ada $10$ cara mengisi persegi panjang tersebut, tetapi perlu diperhatikan bahwa penempatan urutan nilai $a,b,c$ (mewakili persegi panjang dengan ukuran yang disebutkan pada soal) juga mengakibatkan perbedaan cara pengisiannya. Untuk masing-masing cara pada tabel, kita dapat menggunakan permutasi berulang guna menghitung banyak cara seluruhnya, yaitu (untuk setiap barisnya):
$$\begin{aligned} & 1 + \dfrac{5!}{3!.2!} + \dfrac{5!}{1!.2!.2!} + \dfrac{6!}{4!.2!} + \dfrac{5!}{4!.1!} + \dfrac{6!}{3!.2!.1!} + \dfrac{7!}{6!.1!} + \dfrac{6!}{2!.4!} + \dfrac{7!}{5!.2!} + 1 \\ & = 1 + 10 + 30 + 15 + 5 + 60 + 7 + 15 + 21 = 165 \end{aligned}$$

Misalkan pada turnamen tersebut, dua tim yang bertanding adalah Tim A dan Tim B. Tabel berikut menyatakan kemungkinan yang dapat terjadi agar tim A menang ($M$ = menang, $K$ = kalah).
$$\begin{array}{|c|c|c|} \hline \text{Banyak Pertandingan} &  \text{Tim A} &  \text{Tim B} \\ \hline 2 & (M~M) & (K~K) \\ 3 & (K~M~M) & (M~K~K) \\ 4 & (M~K~M~M) & (K~M~K~K) \\ 5 & (K~M~K~M~M) & (M~K~M~K~K) \\ 6 & (M~K~M~K~M~M) & (K~M~K~M~K~K) \\ 7 & (K~M~K~M~K~M~M) & (M~K~M~K~M~K~K) \\ 7 & (M~K~M~K~M~K~M) & (K~M~K~M~K~M~K) \\ \hline \end{array}$$Maksimal pertandingan yang dapat terjadi hanya sampai $7$ kali. Masing-masingnya menghasilkan $2$ kemungkinan, yaitu untuk kemenangan tim A dan untuk kemenangan tim B (tabel di atas hanya merepresentasikan kemenangan tim A). Jadi, ada $7 \times 2 = 14$ cara agar turnamen demikian dapat terjadi.

Gunakan prinsip sarang merpati untuk menyelesaikan kasus ini.
Ada $4$ ukuran baju berbeda. Ambil $6$ helai masing-masing ukuran bajunya, yaitu
$5$ helai baju ukuran S (maksimum),
$4$ helai baju ukuran M (maksimum),
$6$ helai baju ukuran L,
$6$ helai baju ukuran XL.
Jumlah: $5 + 4 + 6 + 6 = 21$ helai baju. Ambil $1$ helai baju lagi (antara baju berukuran L atau XL) sehingga dipastikan kita sudah memegang $7$ helai baju dengan ukuran yang sama. Jadi, kita perlu mengambil paling sedikit $\boxed{22}$ helai baju agar selalu diperoleh $7$ helai baju dengan ukuran yang sama.

Banyak cara menata pose foto $6$ orang berdiri dalam satu baris adalah
$6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$ cara.
Banyak cara menata pose foto $6$ orang sehingga pengantin berdiri saling berdekatan/bersampingan dapat diibaratkan dengan skema berikut.
$\color{red}{OOABCD \Rightarrow XABCD}$
dengan $OO = X$ yang penyusunannya ada $2!$ cara, sedangkan $XABCD$ penyusunannya ada $5!$ cara sehingga totalnya adalah
$2! \times 5! = 2 \times 120 = 240$ cara.
Jadi, banyak cara menata pose foto sehingga pengantin berdiri tidak saling berdekatan/bersampingan adalah $\boxed{720 -240 = 480}$ cara.

Semua kemungkinan ketika huruf X dan Y saling berdekatan dinyatakan dalam bagan berikut.
$$\begin{array}{|c|c|c|c|c|c|c|} \hline X & Y & & & & & \\ \hline  & X & Y & & & & \\ \hline &  & X & Y & & & \\ \hline & & & X & Y & & \\ \hline &  & & & X & Y & \\ \hline & & & & & X & Y \\ \hline \end{array}$$Ada $6$ posisi, dan $XY \neq YX$, berarti total semuanya ada $12$ posisi untuk memenuhi syarat kedua. Masing-masing kotak putih pada setiap baris memiliki pemilihan huruf yang sama dan tak boleh berulang, yaitu
$24 \times 23 \times 22 \times 21 \times 20$ (dimulai dari $24$, karena ada $26$ huruf dan huruf XY telah terpakai).
Jadi, banyak cara membentuk password tanpa pengulangan huruf dan huruf X dan Y berdekatan adalah
$12 \times 24 \times 23 \times 22 \times 21 \times 20.$
Dengan kata lain, banyak cara membentuk password tanpa pengulangan huruf dan huruf X dan Y tidak berdekatan adalah
$$\begin{aligned} & (26 \times 25 \times \cdots \times 20)-(12 \times 24 \times \cdots \times 21 \times 20) \\ & = (26 \times 25 -12) \times 24 \cdots \times 20 \\ & = 638 \times 24 \cdots \times 20 \end{aligned}$$Jadi, peluang membentuk password legal adalah $\boxed{\dfrac{638 \times 24 \cdots \times 20}{26^7}}$

Jumlah wanita di dalam panitia: $2, 3, 4,$ atau $5$ orang.
Pilih $2$ orang dari $5$ wanita, ada $C(5, 2)$ cara, sisanya pilih $3$ orang dari $7$ pria, ada $C(7,3)$ cara.
Pilih $3$ orang dari $5$ wanita, ada $C(5, 3)$ cara, sisanya pilih $2$ orang dari $7$ pria, ada $C(7,1)$ cara.
Pilih $4$ orang dari $5$ wanita, ada $C(5, 4)$ cara, sisanya pilih $1$ orang dari $7$ pria, ada $C(7,2)$ cara.
Pilih $5$ orang dari $5$ wanita, ada $C(5, 5)$ cara, sisanya pilih $0$ orang dari $7$ pria, ada $C(7,0)$ cara.
Jumlah cara pembentukan panitia seluruhnya adalah
$$C(5,2)C(7,3) + C(5,3)C(7,2) + C(5,4)C(7,1) +C(5,5)C(7,0).$$

Kasus di atas dapat dianalogikan sebagai kasus penyusunan huruf-huruf (dalam hal ini, orang). Dalam satu komite, apabila orang yang dipilih sama, tetapi tidak sesuai urutan, tetap akan dianggap sama (analoginya seperti menyusun kata yang memuat sejumlah huruf yang sama). Dengan demikian, ini merupakan kasus permutasi berulang dari $14$ objek. Banyak cara penyusunannya adalah
$\boxed{\dfrac{14!} {3! \cdot 3! \cdot 2! \cdot 2! \cdot 2! \cdot 2!} = 151.351.200}$

Ini merupakan kasus kombinasi dengan pengulangan dengan $n = 4$ (dianalogikan sebanyak $4$ kotak) dan $r = 12$ (dianalogikan sebanyak 12 bola). Setiap kotak bisa diisi $0, 1, 2, \cdots, 12$ bola, dengan syarat jumlah bola pada seluruh kotak yang ada adalah $12$ bola. Contoh penyelesaiannya adalah
$x_1 = 3, x_2 =, 4, x_3 = 3, x_4 = 2.$
Seluruh kemungkinan yang ada adalah
$C(4 + 12 – 1, 12) = C(15, 12) = 455$ solusi.

Analogikan dengan membagi $10$ buah bola yang identik ke dalam $3$ buah kotak, sebut saja kotak $x_1, x_2$, dan $x_3$. Jadi, $x_1$ ada kemungkinan berisi $0$ (tak berisi), $1$, atau $2$. Untuk masing-masing nilai $x_1$, kita perinci perhitungannya sebagai berikut.

1. Kasus $x_1=0$, berarti $x_2+ x_3 = 10.$ Isikan $2$ bola ke dalam kotak $x_2$ (karena syaratnya $x_2 > 1$). Bagikan $8$ bola sisanya ke kotak $x_2$ dan $x_3$, semuanya ada $C(2+8-1,8)=C(9,8)$ cara.
2. Kasus $x_1=1$, berarti $x_2+ x_3 = 9$. Isikan $2$ bola ke dalam kotak $x_2$ (karena syaratnya $x_2 > 1$). Bagikan $7$ bola sisanya ke kotak $x_2$ dan $x_3$, semuanya ada $C(2+7-1,7)=C(8,7)$ cara.
3. Kasus $x_1=2$, berarti $x_2+ x_3 = 8$. Isikan $2$ bola ke dalam kotak $x_2$ (karena syaratnya $x_2 > 1$). Bagikan $6$ bola sisanya ke kotak $x_2$ dan $x_3$, semuanya ada $C(2+6-1,6)=C(7,6)$ cara.

Jumlah solusi seluruhnya adalah $$\boxed{C(9,8) +C(8,7) +C(7,6) = 9 + 8 + 7 = 24}$$

Bilangan $100.000$ jelas tidak memenuhi untuk kasus ini sehingga kita hanya perlu meninjau bilangan dengan $5$ digit (untuk kasus bilangan ratusan, anggap posisi puluh ribuan dan ribuannya $0$, begitu juga untuk kasus bilangan ribuan). Berarti, ada $5$ cara mengisi angka $5, 4$ cara mengisi angka $4$, dan $3$ angka mengisi angka $3.$ Dua tempat kosong lainnya bisa diisi angka lain yaitu $0, 1, 2, 6, 7, 8$, dan $9$ (ada $7$ angka dan boleh berulang). Jadi, banyak bilangan yang demikian adalah $\boxed{5 \times 4 \times 3 \times 7 \times 7 = 2940~\text{cara}}$

Kasus ini adalah kasus kombinasi dengan pengulangan (karena koin tertentu dapat diambil lebih dari sekali). Di sini $n = 4$ dan $r = 5$, berarti banyak cara yang dimaksud adalah $C(4 + 5-1, 5) = C(8,5)$ cara.

(Jawaban a) Pandang setiap topik buku sebagai satu kesatuan (karena harus bersebelahan). Karena ada $4$ topik, jadi kita peroleh $4!$ untuk mengatur susunannya. Di lain sisi, setiap topik memiliki jenis buku yang berbeda pula. Untuk topik matematika, ada $4!$ cara mengatur susunannya, $3!$ cara mengatur susunan buku sejarah, $3!$ cara mengatur susunan buku kimia, dan $2!$ mengatur susunan buku sosiologi. Jadi, totalnya ada
$4! \times 4! \times \times 3! \times 3! \times 2! = 41.472$ cara mengatur susunan buku dengan syarat yang diberikan.
(Jawaban b) Ini termasuk kasus permutasi dengan pengulangan, jadi ada $\dfrac{12!}{4!. 3!. 3!. 2!} = 277.200$  cara mengatur susunan bukunya.

Ingatlah kembali definisi fungsi bahwa setiap elemen pada himpunan $A$ (domain) harus mempunyai pasangan tepat satu di himpunan $B$ (kodomain). Elemen pertama di $A$ mempunyai $n$ kemungkinan peta di $B,$ begitu juga elemen kedua, elemen ketiga, sampai elemen ke-$m$ sehingga jumlah fungsi yang dapat dibuat dari $A$ ke $B$ (terapkan aturan perkalian) adalah $\underbrace{n \times n \times\cdots \times n} _{\text{sebanyak}~m} = n^m$ buah.

Huruf vokal pada kata $SARUNG$ adalah $A$ dan $U$. Hal yang ditanyakan dalam soal ini adalaah untaian yang mengandung $UA$ atau $AU$. Karena $UA$ atau $AU$ harus muncul pada satu blok, maka kita harus menghitung jumlah permutasi blok $AU$ atau $UA$ dengan huruf-huruf $S, R, N$, dan $G$. Untuk $AU,S, R, N$, dan $G$, jumlah kata yang dapat dibentuk adalah $P(5,5)=5!$, begitu juga untuk $UA, S, R, N$, dan $G$.
Jadi, jumlah untaian seluruhnya adalah $5! + 5! = 240.$

Jumlah cara mengambil $5$ kartu sembarang dari $52$ kartu yang ada adalah $C(52,5)$ (jumlah titik contoh).
Jumlah cara mengambil satu jenis kartu dari $13$ jenis yang ada adalah $C(13,1)$.
Jumlah cara mengambil $4$ kartu dari $4$ kartu sejenis adalah $C(4,4)$.
Jumlah cara mengambil satu kartu lagi dari sisa $48$ kartu lainnya adalah $C(48,1)$.
Jadi, peluang dari $5$ kartu tersebut mengandung $4$ kartu sejenis adalah
$$\boxed{\dfrac{C(13,1) \times C(4,4) \times C(48,1)} {C(52,5)} = 0,00024}$$

Pada soal ini, jenis kartu sudah ditentukan, yaitu kartu as, jadi hanya ada satu cara (pilihan) untuk mengambilnya.
Jumlah cara mengambil $4$ kartu dari $4$ kartu as adalah $C(4,4)$.
Jumlah cara mengambil $1$ kartu lagi dari $48$ kartu sisanya adalah $C(48,4)$
Jumlah cara mengambil $5$ kartu sembarang dari $52$ kartu adalah $C(52,5)$.
Jadi, peluang dari $5$ kartu itu mengandung $4$ kartu as adalah
$$\boxed{\dfrac{1 \times C(4,4) \times C(48,1)} {C(52,5)} = 0,0000185}$$

Soal ini termasuk kasus kombinasi dengan pengulangan ketika $n = 3$ dan $r = 10$. Jumlah cara memilih buku adalah
$C(3 + 10 – 1, 10) = C(12, 10) = 66.$

Langkah pertama adalah memasangkan setiap angka $0$ dengan angka $1$. Berdasarkan informasi pada soal, kita akan memperoleh tepat $8$ pasangan yang mungkin (angka $01$ sebanyak $8$ kali kemunculan) dan sisanya adalah angka $1$ sebanyak $2$ buah. Perhatikan ilustrasi tabel berikut.
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & 01 & & 01 & & 01 & & 01 & & 01 & & 01 & & 01 & & 01 & \\ \hline \end{array}$$Ilustrasi tabel di atas menunjukkan bahwa ada $9$ kotak putih yang dapat kita tempatkan angka $1$ tersisa. Jadi, ada $C(9,2) = 36$ cara memposisikannya (menggunakan kombinasi, karena bila angka $1$ dan angka $1$ yang lain dibolak-balik dianggap sama, tetap membentuk $11$). Ini hanya cara ketika angka $1$ dan angka $1$ yang lain diletakkan secara terpisah dalam kotak itu. Ada kemungkinan angka $1$ dan angka $1$ yang lain diletakkan dalam kotak yang sama, sebab akan menghasilkan digit biner yang berbeda, contohnya $$11-01-01-01-01-01-01-01-01.$$Karena ada $9$ kotak, maka ada $9$ cara lain yang dimaksud.
Jadi, ada $36 + 9 = 45$ rangkaian digit biner berbeda yang dapat dibuat dengan syarat yang diberikan.

Kasus ini ekuivalen dengan kasus penyusunan untaian yang mengandung sejumlah huruf yang sama. Gunakan permutasi berulang untuk kasus ini, yaitu $\dfrac{14!}{(3!)^2\times (2!)^3}.$
Jadi, banyaknya pose foto berdiri dalam satu baris pada 14 anak tersebut adalah $\boxed{\dfrac{14!}{(3!)^2\times (2!)^3}}$

Berdasarkan syarat yang diberikan, akan ada $1$ pegawai yang mendapat $2$ pekerjaan, sedangkan $3$ pegawai lainnya mendapatkan $1$ pekerjaan. Kondisinya diberikan oleh tabel di bawah dengan angka-angkanya mewakili banyak pekerjaan yang diambil.
$$\begin{array}{|c|c|c|c|} \hline \text{Pegawai 1} & \text{Pegawai 2} & \text{Pegawai 3} & \text{Pegawai 4} \\ \hline 2 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 1 & 1 & 2 \\ \hline \end{array}$$Untuk kondisi pertama, pegawai $1$ mendapatkan $2$ pekerjaan, sedangkan $3$ pegawai lainnya mendapatkan $1$ pekerjaan saja. Untuk pegawai $1$, banyak cara ia memilih $2$ dari $5$ pekerjaan yang tersedia adalah $C(5, 2) = \dfrac{5!}{3! \cdot 2!} = 10$ cara. Tersisa $3$ pekerjaan untuk $3$ orang pegawai lainnya. Banyak cara pemberian pekerjaan ini dapat dihitung dengan aturan permutasi, yaitu $P(3, 3) = 3! = 6$ cara. Banyak cara untuk kondisi pertama adalah $10 \times 6 = 60$ cara. Karena ada $4$ kondisi berbeda, maka banyak cara seluruhnya ada $\boxed{4 \times 60 = 240}$ cara.

Misalkan
$$S = \displaystyle \dfrac{1}{n} \binom{n} {1}+\dfrac{2}{n} \binom{n} {2}+\cdots+\dfrac{n-1}{n} \binom{n} {n-1}.$$Dengan menggunakan sifat kesimetrisan binomial, diperoleh
$$S = \displaystyle \dfrac{1}{n} \binom{n} {n-1}+\dfrac{2}{n} \binom{n-2} {2}+\cdots+\dfrac{n-1}{n} \binom{n} {1}.$$Jumlahkan keduanya sehingga didapat
$$2S = \displaystyle \binom{n} {1} + \binom{n} {2} + \cdots + \binom{n} {n-1} = \sum_{k=1}^{n-1} \binom{n} {k}.$$Ingat teorema binomial berikut.
$\boxed{\displaystyle \sum_{k=0}^{n} \binom{n} {k} x^ky^{n-k} = (x+y)^n}$
Dengan mengganti $x = y = 1$, kita akan mendapatkan bahwa
$2^n = \displaystyle \sum_{k=0}^{n} \binom{n} {k}.$
Karena $\displaystyle \binom{n}{0} =\binom{n} {n} = 1$, kita akan mendapatkan
$2S = 2^n -2 \Rightarrow \boxed{S = 2^{n-1} -1}$

Misalkan $a_1$ adalah banyaknya latih tanding yang telah dilakukan petinju sampai hari ke-$i$ dengan $i = 1,2,3,\cdots, 75$ sehingga diperoleh
$1 \leq a_1 < a_2 < a_3 < \cdots < a_{75} \leq 125$
dan dengan menambahkan $24$ di setiap ruas, diperolehlah
$$25 \leq a_1 + 24 < a_2+24< \cdots < a_{75} + 24 \leq 149$$Karena ada 149 bilangan terhitung dari 1 sampai 149, sedangkan $$a_1,a_2,a_{75},a_1+24,a_2+24, \cdots, a_{75}+24$$ ada 150 bilangan, maka menurut prinsip sarang merpati, setidaknya ada 2 bilangan yang sama dari barisan tersebut, yakni ada $i$ dan $j$ sehingga $a_i = a_j +24.$
Dengan kata lain, pada hari ke $j+1,j+2,\cdots, i$, si petinju tepat latih tanding sebanyak $24$ kali.

Dengan menggunakan pembuktian kombinatorial, misalkan terdapat $2n$ orang dalam suatu grup yang terdiri dari $n$ pria dan $n$ wanita. Kita hendak memilih $5$ orang perwakilan dari grup tersebut sehingga banyak cara memilihnya adalah $\displaystyle \binom{2n} {5}.$
Di lain sisi, perwakilan tersebut dapat terdiri dari pria (P) dan wanita (W) dengan kombinasi 5P, 5W, 4P 1W, 3P 2W, 2P 3W, dan 1P 4W. Banyak cara memilih perwakilan tersebut dengan menggunakan aturan perkalian dan penjumlahan adalah 
$$\begin{aligned} & \displaystyle \binom{n} {5} \binom{n} {0} + \binom{n}{0} \binom{n}{5} + \binom{n} {4}\binom{n} {1} + \binom{n} {3}\binom{n} {2} + \binom{n} {2} \binom{n} {3} + \binom{n} {1} \binom{n} {4} \\ & = 2 \binom{n} {5} \binom{n} {0} + 2 \binom{n} {4}\binom{n} {1} + 2 \binom{n} {3}\binom{n} {2} \\ & = 2 \binom{n} {5} + 2n \binom{n} {4} + (n^2-n) \binom{n}{3}. \end{aligned}$$Jadi, terbukti bahwa
$$\displaystyle \binom{2n} {5} = 2\binom{n} {5} + 2n\binom{n}{4} + (n^2-n) \binom{n} {3}.$$ $\blacksquare$

Ubah bentuk persamaan kombinatorialnya dengan menggunakan sifat kesimetrisan koefisien binomial.
$$\displaystyle \binom{m+n} {n} = \binom{m} {0}\binom{n} {n} + \binom{m} {1}\binom{n} {n-1} + \cdots + \binom{m} {n} \binom{n} {0}$$Dengan menggunakan pembuktian kombinatorial, misalkan terdapat subhimpunan $S$ dengan $n$ elemen dari himpunan $H$ beranggotakan $m+n$ elemen. Banyak subhimpunan yang dapat dibentuk adalah $\displaystyle \binom{m+n} {n}.$ Di lain sisi, anggap $H = A \cup B$ dengan $A \cap B = \emptyset.$ Misalkan $|A| = m$ dan $|B| = n.$ Subhimpunan $S$ dapat dikonstruksi dengan cara: (1) mengambil $0$ elemen dari $A$ dan $n$ elemen dari $B$; (2) mengambil $1$ elemen dari $A$ dan $n-1$ elemen dari $B$; (3) mengambil $2$ elemen dari $A$ dan $n-2$ elemen dari $B$; dan seterusnya sampai mengambil $n$ elemen dari $A$ dan $0$ elemen dari $A.$ Dengan menggunakan aturan perkalian dan penjumlahan, diperoleh banyak subhimpunan $S$ berbeda, yaitu
$$\displaystyle\binom{m} {0}\binom{n} {n} + \binom{m} {1}\binom{n} {n-1} + \cdots + \binom{m} {n} \binom{n} {0}.$$Dengan menggunakan sifat kesimetrisan koefisien binomial, diperoleh
$$\binom{m} {0}\binom{n} {0} + \binom{m} {1}\binom{n} {1} + \cdots + \binom{m} {n} \binom{n} {n}.$$Jadi, terbukti bahwa $$\displaystyle \binom{m+n}{n} = \binom{m} {0}\binom{n} {0} + \binom{m} {1}\binom{n} {1} + \cdots + \binom{m} {n} \binom{n} {n}.$$ $\blacksquare$

Jika kedelapan bilangan bulat tersebut dibagi $12$, maka kemungkinan sisanya adalah $\{0,1,2,\cdots, 12\}$. Sekarang siapkan $7$ buah “kotak” dan beri label seperti berikut.
$$\{0\}, \{1,11\}, \{2,10\}, \{3,9\}, \{4,8\}, \{5,7\}, \{6\}$$Kemudian kita masukkan kedelapan bilangan bulat itu ke dalam “kotak” sesuai dengan sisa hasil baginya oleh $12$. Karena terdapat $7$ buah kotak dan $8$ bilangan, maka menurut prinsip sarang merpati, terdapat setidaknya satu kotak yang memuat dua bilangan. Jika kotak itu adalah kotak berlabel $\{0\}$ dan $\{6\}$, maka selisih dua bilangan tersebut adalah kelipatan $12$, contohnya bilangan $6$ dan $12$ yang masuk ke kotak berlabel $\{6\}$ (karena sisa hasil baginya oleh $12$ adalah $6$) memiliki selisih $12$. Di lain sisi, jika yang memuat dua bilangan itu kotak lainnya, maka hasil penjumlahan dua bilangan tersebut habis dibagi $12$, contohnya bilangan $2$ dan $22$ masuk ke dalam kotak berlabel $\{2,10\}$ memiliki jumlah $24$, yang merupakan kelipatan $12.$ (Terbukti) $\blacksquare$

Ingat identitas binomial berikut.
$\boxed{\begin{aligned} & \displaystyle \sum_{k=1}^{n} k^2\binom{n} {k} = (n+n^2)2^{n-2} \\ & \sum_{k=1}^{n} k\binom{n} {k} = n2^{n-1}\end{aligned}} $
Dengan menggunakan identitas tersebut, diperoleh
$$\begin{aligned} \displaystyle \sum_{k=2}^{n} k(k-2) \binom{n} {k} & = \sum_{k=2}^{n} k^2 \binom{n}{k} -2 \sum_{k=2}^{n} k\binom{n} {k} \\ & = \sum_{k=1}^{n} k^2 \binom{n} {k} -2\sum_{k=1}^{n} k\binom{n} {k}- \left(1^2\binom{n} {1} -2\binom{n} {1}\right) \\ & = (n+n^2)2^{n-2} -2n \cdot 2^{n-1} -(n-2n) \\ & = 2^{n-1}\left(-\dfrac{3}{2}n+\dfrac{1}{2}n^2\right)+n \end{aligned}$$

Misalkan $A$ adalah himpunan permutasi dari $0,1,2,\cdots, 9$ yang diawali oleh digit $987$,
$B$ adalah himpunan permutasi dari $0,1,2,\cdots, 9$ yang memuat digit $45$ pada posisi ke-$5$ dan $6$, dan $C$ adalah himpunan permutasi dari $0,1,2,\cdots, 9$ yang diakhiri oleh digit $123$ sehingga diperoleh $|A| = 7!$ karena ada $7$ posisi lainnya yang dapat diisi digit yang masih tersedia, $|B| = 8!$ dan |C|=7!.$
Perhatikan juga bahwa $|A \cap B| = 5!$ hanya tersisa $5$ posisi yang dapat diisi angka yang masih tersedia, begitu juga  $|A \cap C| = 5!$ dan $|B \cap C| = 5!.$
Terakhir,  $|A \cap B \cap C|= 2!$ karena hanya ada $2$ posisi (yaitu posisi ke-$4$ dan $7$) yang masih dapat diisi angka yang tersedia (yaitu $0$ dan $6$). Berdasarkan prinsip inklusi-eksklusi, diperoleh
$$\begin{aligned} |A \cup B \cup C| & = |A| +|B|+|C| – |A \cap B| – |A \cap C| -|B \cap C| + |A \cap B \cap C| \\ & = 7! + 8! + 7! – 5! – 4! – 5! + 2! = \boxed{50138} \end{aligned}$$Jadi, ada $50138$ permutasi dari bilangan $0$ sampai $9$ dengan kondisi yang disebutkan di atas.

Andaikan ada $n$ peserta seminar, yaitu $k_0, k_1, k_2, \cdots, k_{n-1}$, dengan $k_i$ menyatakan peserta seminar yang memiliki $i$ kenalan dan berbeda-beda. Ini berarti, $k_0$ adalah peserta seminar yang tidak memiliki kenalan sama sekali, $k_1$ adalah peserta seminar yang hanya memiliki $1$ kenalan, dan seterusnya, sampai $k_{n-1}$ adalah peserta seminar yang memiliki $n-1$ kenalan. Jelas ini kontradiksi karena $k_{n-1}$ memiliki kenalan dengan semua peserta seminar yang ada, termasuk dengan $k_0$, padahal $k_0$ tidak memiliki kenalan. Jadi, pengandaian diingkari. Terbukti bahwa selalu terdapat setidaknya dua orang peserta seminar yang memiliki jumlah kenalan yang sama.

Gunakan Euler’s totient function. Misalkan suatu bilangan bulat positif $n$ dapat dituliskan dalam bentuk faktorisasi prima, yaitu
$n = p_1^{k_1} + p_2^{k_2} + \cdots + p_r^{k_r}.$
sehingga banyaknya bilangan kurang dari $n$ yang relatif prima dengannya adalah $$\psi(n) = n\left(1-\dfrac{1}{p_1}\right)\left(1-\dfrac{1}{p_2}\right)\cdots \left(1-\dfrac{1}{p_r}\right).$$Karena $210 = 2 \times 3 \times 5 \times 7$, maka banyak bilangan kurang dari $210$ dan relatif prima dengannya adalah
$$\begin{aligned} \psi(210) & = 210\left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)\left(1-\dfrac{1}{5}\right)\left(1-\dfrac{1}{7}\right) \\ & = 210\left(\dfrac{1}{2}\right) \left(\dfrac{2}{3}\right) \left(\dfrac{4}{5}\right) \left(\dfrac{6}{7}\right) = 48. \end{aligned}$$Jadi, banyaknya bilangan yang relatif prima dengan $210$ dan kurang darinya adalah $48$.

Nilai $(a, b, c)$ pada persamaan $a! +b! =c!$ dipenuhi oleh $(0,0,2), (1,0,2),$ $(0,1,2),$ dan $(1,1,2).$ Misalkan $c$ adalah bilangan bulat positif yang lebih dari dua, sebutlah $n,$ dengan $n > 2$. Sekarang, ambil $a = b = n -1,$ yang merupakan pasangan bilangan terbesar agar bila dijumlahkan dapat mencapai nilai di ruas kanan. Jadi, dapat ditulis
$\begin{aligned} & (n-1)! + (n-1)! = n! \\ & 2(n-1)! < n(n-1)! = n!. \end{aligned}$
Jadi, tidak ada nilai $c$ yang dipenuhi oleh $a$ dan $b$ sehingga persamaan itu benar. Dengan demikian, hanya ada $4$ pasangan bilangan $(a, b, c)$ yang memenuhi persamaan $a! + b! = c!$.

Berdasarkan prinsip paritasnya (genap-ganjil), terdapat $2^4 = 16$ jenis kombinasi paritas untuk koordinat $(w_i, x_i, y_i, z_i)$. Karena terdapat $17$ titik, berdasarkan Pigeonhole Principle ada dua titik yang paritasnya berjenis sama. Misal kedua titik ini adalah $A = (w_i, x_i, y_i, z_i)$ dan $B = (w_j, x_j, y_j, z_j).$ Akibatnya, $w_i + w_j, x_i + x_j, y_i + y_j,$ dan $z_i + z_j$ adalah bilangan genap (ganjil + ganjil = genap, begitu juga genap + genap = genap). Dengan demikian, titik tengah dari garis lurus yang menghubungkan $A$ dan $B$, sebut saja $C$, memiliki koordinat $$C = \left(\dfrac{w_i + w_j} {2},\dfrac{x_i + x_j} {2},\dfrac{y_i + y_j} {2}, \dfrac{z_i + z_j} {2}\right)$$ adalah titik latis (karena bilangan genap bila dibagi $2$ hasilnya adalah bilangan bulat). $\blacksquare$
Catatan: Salah satu kombinasi paritas yang dimaksud pada koordinat itu adalah $(w_1, x_1, y_1, z_1)$ dengan $w_1$ genap, $w_2$ ganjil, $w_3$ genap, dan $w_4$ ganjil. Banyaknya kombinasi paritas seluruhnya ada $16$.

Ingatlah identitas binomial berikut.
$\boxed{\begin{aligned} & \displaystyle \binom{n} {0} = \binom{n-1}{0} = 1 \\ & \binom{n} {k} + \binom{n} {k+1}= \binom{n+1}{k+1} \end{aligned}}$
Dengan menguraikannya dalam bentuk jumlah, diperoleh
$$\begin{aligned}\displaystyle \sum_{k=0}^{r} \binom{n+k-1}{k} & = \binom{n-1}{0} + \binom{n} {1} + \binom{n+1}{2} + \cdots + \binom{n+r-1}{r} \\ & = \binom{n+1}{1} + \binom{n+1}{2} + \binom{n+2}{3} + \cdots + \binom{n+r-1}{r} \\ & = \binom{n+2}{2} + \binom{n+2}{3} + \cdots + \binom{n+r-1}{r} \\ & = \binom{n+r} {r}. \end{aligned} $$Jadi, didapat $\boxed{\displaystyle \sum_{k=0}^{r} \binom{n+k-1}{k} = \binom{n+r}{r}} $

Dengan menggunakan teorema binomial
$\displaystyle \sum_{k=0}^{100} \binom{100}{k} x^{100-k} \left(\dfrac{1}{x}\right)^{k},$
maka ekspresi dari $x^{80}$ pada ekspansi tersebut ditentukan saat $k = 10$, yaitu
$\displaystyle \binom{100}{10}x^{90}\left(-\dfrac{1}{x}\right)^{10} = \binom{100}{10}x^{80}.$
Jadi, koefisien dari $x^{80}$ pada ekspansi tersebut adalah $\boxed{\binom{100}{10}}$ 

Kelipatan persekutuan terkecil dari $3, 4$, dan $6$ adalah $12$ sehingga banyak bilangan yang habis dibagi tiga bilangan itu sama dengan banyak bilangan yang habis dibagi $12$, yaitu $\displaystyle \left \lfloor\dfrac{500}{12}\right \rfloor = \lfloor 41,\cdots \cdot \rfloor = 41$.
Jadi, banyak bilangan yang tidak habis dibagi $3, 4$, dan $6$ adalah $500-41 = 459$.

Fungsi rekursif $f(n+1)=f(n)+2f(n-1)$ ekuivalen dengan $f(n)=f(n-1)+2f(n-2)$ atau ditulis menjadi $f(n) -f(n-1) – 2f(n-2)=0$. Relasi di atas termasuk relasi rekursif homogen dengan koefisien konstan, dengan persamaan karakteristik
$r^2 -r -2r = (r -2)(r+1) = 0.$
Diperoleh $r = 2$ atau $r = -1.$
Jadi, solusi relasinya adalah
$f(n) = C_12^n + C_2(-1)^n.$
Substitusikan $f(1) = 1$ dan $f(2) = 5$ berturut-turut untuk mendapatkan
$1 = C_1(2) + C_2(-1)$ dan $5 = C_1(4) + C_2.$
Gunakan metode penyelesaian SPLDV untuk mendapatkan $C_1 = C_2 = 1$ sehingga $\boxed{f(n) = 2^n + (-1)^n}$

Himpunan ganda (multiset) adalah himpunan yang boleh berisikan anggota yang sama (anggota yang sama ditulis tidak harus satu kali) . Sebagai contoh, himpunan $\{0, 0,1,1,2\}$ merupakan himpunan ganda. Lima belas kombinasi himpunan ganda di sini berarti kita harus mencari kombinasi anggota himpunan sehingga kardinalitas himpunannya sebanyak $15$.
Kasus ini dapat kita ibaratkan sebagai suatu persamaan,
$x_1 + x_2 + \cdots + x_{10} = 15 + 10 = 25$
dengan $x_i \geq 1, 1 \leq i \leq 10$, $x_1$ mewakili banyaknya elemen $a$ yang muncul, $x_2$ mewakili banyaknya elemen $1$, dan seterusnya. Dengan menggunakan Dalil Kombinatorik de Moivre, banyak solusi bulatnya adalah $\displaystyle \binom{25 -1}{10-1} =\binom{24}{9}.$
$\bigstar$ Dalil Kombinatorik de Moivre ampuh dalam menjawab banyaknya solusi bulat yang memenuhi suatu persamaan linear.
Jika $x_1, x_2, \cdots, x_k$ memenuhi persamaan
$x_1 + x_2 + \cdots + x_k = n$
dengan syarat $x_i \geq 1, 1 \leq i \leq k, n \in \mathbb{N}$, maka banyaknya solusi bulat yang memenuhi persamaan tersebut adalah $\boxed{\displaystyle \binom{n -1}{k -1}}$

Untuk mendapatkan sepasang kaos kaki sewarna, berarti kita harus mengambil setidaknya $2$ kaos kaki, tetapi belum dapat dipastikan kita mendapatkannya.
Berdasarkan prinsip sarang merpati, untuk memastikan diperolehnya sepasang kaos kaki sewarna, maka kita hanya perlu mengambil paling sedikit $2 + 1 = 3$ kaos kaki.

Misalkan $M, K, G$ berturut-turut menyatakan himpunan mahasiswa yang mengambil mata kuliah Matematika Diskrit, Kalkulus, dan Geometri.
Berdasarkan prinsip inklusi-eksklusi, diperoleh
$$ |M \cap K \cap G| = 196 -(115 + 71 + 56) + (25 + 14 + 9) = 2.$$Jadi, ada $2$ mahasiswa yang mengambil tiga mata kuliah itu sekaligus.

Berdasarkan prinsip inklusi-eksklusi, diperoleh
$$\begin{aligned} & |A \cup B \cup C  \cup D| \\ & = (4 \times 50) -(6 \times 30) + (4 \times 10) -2 \\ & = 58. \end{aligned}$$Catatan: Angka $4, 6, 4$ masing-masing mewakili banyaknya kombinasi susunan himpunan berdasarkan jumlahnya. Sebagai contoh, banyaknya kombinasi memilih $2$ himpunan dari $4$ himpunan adalah $C_2^4 = \dfrac{4!} {2!2!} = 6.$
Jadi, banyak anggota dari $|A \cup B \cup C \cup D|$ adalah $58$.

Dengan menggunakan permutasi berulang (sebab ada huruf yang sama), banyak cara penyusunan kata SUCCESS adalah
$\boxed{\dfrac{7!}{3!2!} = \dfrac{7 \times 6 \times 5 \times 4}{2} = 420}$
dengan bilangan 7, 3, dan 2 berturut-turut menyatakan banyaknya huruf pada kata SUCCESS, banyak huruf S, dan banyak huruf C.

Ingat bahwa barisan bit hanya berupa barisan dengan digit $0$ dan $1$. Karena ada $10$ bit, maka akan ada $2^{10} = 1024$ kemungkinan bit yang berbeda, salah satunya adalah bit-bit yang semua digitnya adalah satu ($1111111111$) sehingga bit lainnya pasti setidaknya mengandung satu digit nol. Jadi, peluang paling sedikit satu dari bit-bit tersebut adalah bit nol sebesar
$\boxed{\dfrac{1024-1}{1024}= \dfrac{1023}{1024}} $

(Alternatif: Pendekatan Integral)
Misalkan $H_n = 1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n}.$
Ingat bahwa $\dfrac{1-x^n} {1-x} = 1 + x + x^2 + \cdots + x^{n-1}.$
Dari persamaan itu, dapat dilihat bahwa $H_n = \displaystyle \int_0^1 \dfrac{1-x^n} {1-x}~\text{d}x.$
Selanjutnya, substitusikan $x = 1 – u$, diperoleh
$$\begin{aligned} H_n & = – \displaystyle \int_0^1 \dfrac{1 – (1 – u)^n} {u}~\text{d}u \\ & = -\int_0^1 \left(\dfrac{1}{x} – \dfrac{\displaystyle \sum_{k=0}^n (-u)^k\binom{n} {k}}{u} \right)~\text{d}u~~\bigstar\\ & = \int_0^1 \sum_{k=1}^n (-1)^{k-1}u^{k-1}\binom{n}{k}~\text{d}u~~\bigstar \bigstar\\ & = \sum_{k=1}^n (-1)^{k-1}\binom{n} {k} \int_0^1 u^{k-1}~\text{d}u \\ & = \sum_{k=1}^n (-1)^{k-1}\dfrac{1}{k} \binom{n} {k} \end{aligned}$$(Terbukti)
Catatan:
$\bigstar$ Ingat teorema binomial bahwa
$\boxed{(x+y)^n = \sum_{k=0}^n x^ky^{n-k}\binom{n} {k}}.$
Jika $x$ diganti menjadi $-x$ dan $y = 1$, diperoleh
$(1 – x)^n = \displaystyle \sum_{k=0}^n (-x)^k\binom{n} {k}.$
$\bigstar \bigstar$ Perhatikan bahwa indeks batas bawah sumasi berubah dari $0$ menjadi $1$. Hal ini dikarenakan adanya penjabaran nilai untuk $k = 0$, yang menghasilkan $\dfrac{1}{x}$ sehingga mengeliminasi suku di depannya.

Soal ini tergolong permasalahan yang dapat diatasi dengan menggunakan teorema Bayes. 
Misalkan tas yang isinya $5$ jeruk dan $20$ apel disebut tas besar (large), sedangkan tas lainnya disebut tas kecil (small). Diagram pohon berikut dapat menjadi model dari masalah di atas.

Sekarang, misalkan $L$ dan $S$ berturut-turut adalah kejadian terambilnya sejumlah tas besar dan tas kecil, sedangkan $O$ dan $A$ berturut-turut adalah kejadian terambilnya sebuah jeruk dan apel. 
Jawaban a) 
Peluang terambilnya sebuah apel dinyatakan oleh
$$\begin{aligned} P(A) & = P(L \cap A) + P(S \cap A) \\ & = P(L). P(A|L) + P(S). P(A|S) \\ & = 0,6 \times \dfrac{20}{25} + 0,4 \times \dfrac{10}{25} = 0,64. \end{aligned}$$Jadi, peluang terambilnya sebuah apel adalah $0,64$. 
Jawaban b) 
Jika sebuah apel diambil, maka peluang apel itu terambil dari sejumlah tas besar (tas yang berisikan $5$ jeruk dan $20$ apel) dinyatakan oleh
$$\begin{aligned} P(L|A) & = \dfrac{P(L \cap A)} {P(A)} \\ & = \dfrac{P(L). P(A|L)} {P(A)} \\ & = \dfrac{0,6 \times \dfrac{20}{25}} {0,64} \\ & = 0,75. \end{aligned}$$Jadi, peluang yang dimaksud sebesar $0,75$. 
Catatan:
Teorema Bayes (Bayes’ Theorem) adalah salah satu teorema dalam teori peluang dan statistik yang menyatakan peluang suatu kejadian berdasarkan syarat (kejadian lain) yang telah diketahui sebelumnya, karena adanya kemungkinan bahwa kejadiannya berkaitan. Kata “Bayes” sendiri diambil dari nama pembuat rumusnya, Thomas Bayes (1701-1761). 
Perumusan teorema Bayes adalah sebagai berikut. 
$\boxed{P(A|B) = \dfrac{P(B|A) \times P(A)} {P(B)}}$

Diketahui
$$\begin{aligned} S_n & = \displaystyle \sum_{r =0}^{n} \dfrac{1}{C_r^n} \\ & = \dfrac{1}{C_0^n} + \dfrac{1}{C_1^n} + \cdots + \dfrac{1}{C_n^n} \\ T_n & = \displaystyle \sum_{r =0}^{n} \dfrac{r}{C_r^n} \\ & = \dfrac{0}{C_0^n} + \dfrac{1}{C_1^n} + \dfrac{2}{C_2^n} \cdots + \dfrac{n}{C_n^n} && (\cdots 1) \end{aligned}$$Kita bisa tuliskan $T_n$ dengan menyusunnya sebagai berikut.
$$\begin{aligned} T_n & = \dfrac{n}{C_n^n} + \dfrac{n-1}{C_{n-1}^n} + \cdots + \dfrac{1}{C_1^n} \cdots + \dfrac{0}{C_0^n} \\ & = \dfrac{n}{C_0^n} + \dfrac{n-1}{C_1^n} + \cdots + \dfrac{1}{C_{n-1}^n} \cdots + \dfrac{0}{C_n^n} && (\cdots 2) \end{aligned}$$Ingat: $C_0^n = C_n^n$, $C_1^n = C_{n-1}^n$, dan seterusnya.
Dengan menjumlahkan persamaan $(1)$ dan $(2)$, diperoleh
$$\begin{aligned} 2T_n & = \dfrac{n}{C_0^n} + \dfrac{n}{C_1^n} + \cdots + \dfrac{n}{C_{n-1}^n} + \dfrac{n}{C_n^n} \\ 2T_n & = n \left(\dfrac{1}{C_0^n} + \dfrac{1}{C_1^n} + \cdots + \dfrac{1}{C_n^n}\right) \\ 2T_n & = n \cdot S_n \\ \dfrac{T_n}{S_n} & = \dfrac{n}{2} \end{aligned}$$Jadi, nilai dari $\boxed{\dfrac{T_n}{S_n} = \dfrac{n}{2}}$
(Jawaban D)